The present application is related to decoders for decompressing Huffman-coded data and, more particularly, to the architecture of high-speed decoders of Huffman-coded data.
In Huffman coding, units of original data are compressed into coded units consisting of codewords of varying lengths and optional non-Huffman coded words. The codewords are selected so that the most frequently occurring units of original data have the shortest length, i.e., the smallest number of bits, and the least frequently occurring units of original data have the largest codewords. In this manner, the original data is compressed into coded data. This is a general description of Huffman coding techniques and, of course, the selection and generation of Huffman codes for particular applications may be expressed with much greater precision.
The application of Huffman coding is typically used where there is a large amount of data which must be processed or transferred, such as digital image processing. For example, color images processed according to the JPEG (Joint Photographic Experts Group) standard, and the standard's Huffman coding, typically handle a large number of data units. Huffman coding is found in present and emerging digital video processing standards.
Included in these standards is the previously mentioned JPEG standard, which is a standard for still images. Existing and emerging standards for motion video systems, such as H.261, a CCITT video teleconferencing standard, and the Motion Picture Experts Group (MPEG) I, have coding systems which are very similar to the JPEG standard. In turn, the MPEG standards are related to the nascent High Definition Television (HDTV) technology. The commonality between HDTV, MPEG, H.261 and JPEG is expected to include Huffman coding.
Where Huffman coding is used, decoding of the Huffman-coded units must naturally be performed. In the decoding of each coded unit, a token is generated from each codeword. Each token, because it is unique, contains enough information about the coded unit (and original data unit) to be used as control information to assemble, or decompress, the coded unit into the original data unit.
A significant and fundamental problem is found in the decoding operation which generates each token from a codeword. The problem arises when high-speed decoding of the coded units is required. In decoding a stream of Huffman-coded units in a typical Huffman decoder, each unit contains a codeword and optional non-code words of varying length, which creates difficulty for high-speed decoding.
This difficulty in decoding Huffman-coded data at high speed poses a serious impediment to emerging technology. As explained above, it is likely that the emerging digital HDTV standards will incorporate Huffman coding. An estimate of HDTV requirements leads to the processing of pixel components at 100 million data units per second. To solve this problem, the present invention provides for novel Huffman decoding architectures in which coded units are decoded in parallel.
Various embodiments for Huffman decoder architectures are presented. These Huffman decoder architectures, all capable of high-speed operation, use differing amounts of memory and logic. The balance of memory and logic has different space/speed tradeoffs in the particular technology implemented by an integrated circuit designer. Thus the present invention offers high-speed alternatives for most, if not all, of the specific applications of Huffman decoders. The present invention permits the selection of the optimum decoder architecture.